package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/palindromic-substrings/
 */
public class Title647 {

    /**
     * dp[i][j]表示[i,j]范围的字符子串是否为回文串
     * 递推公式：
     *                   s[i] != s[j] false;
     *                   s[i] == s[j]:
     *                            3、i==j true
     *                            2、if(d[i+1][j-1]==true) dp[i][j] = true else false;
     *                            1、j = i + 1 true
     * @param s
     * @return
     */
    public static int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int count = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j || j == i + 1) {
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                    }
                    if (dp[i][j]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    public int countSubstrings1(String s){
        //abc 判断  a b c  ab  bc abc  以某点/相邻点为中心扩散（奇数，偶数）
        int result = 0;
        for(int i = 0; i < s.length(); i++){
            result += expand(s, i, i);
            result += expand(s, i, i + 1);
        }
        return result;
    }

    private int expand(String s, int i, int j) {
        int n = s.length();
        int count = 0;
        while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
            count++;
        }
        return count;
    }


    public static int countSubstrings3(String s) {
        int n = s.length();
        //dp[i][j]表示区间[i,j]是否为回文串
        // if dp[i+1][j-1]是回文, s.charAt(i)==s.charAt(j) , dp[i][j]==true
        boolean[][] dp = new boolean[n][n];
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i == j || i + 1 == j) {
                        dp[i][j] = true;
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                    }
                    if (dp[i][j]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        countSubstrings3("aaa");
    }
}
